import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.List;

/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution95 {

    public static void main(String args[]) {
        Solution95 s = new Solution95();
        List<TreeNode> ret = s.generateTrees(0);
        for (TreeNode t : ret) {
            System.out.println(t);
        }
    }

    public List<TreeNode> generateTrees(int n) {
        if(n == 0){
            return new ArrayList<TreeNode>();
        }
        return dfs(1, n);
    }

    public List<TreeNode> dfs(int l, int r) {
        List<TreeNode> ret = new ArrayList<>();
        if (l == r) {
            TreeNode t = new TreeNode(l);
            ret.add(t);
            return ret;
        }
        if (l > r) {
            ret.add(null);
            return ret;
        }

        for (int i = l; i <= r; i++) {
            List<TreeNode> lr = dfs(l, i - 1);
            List<TreeNode> rr = dfs(i + 1, r);
            TreeNode mid = new TreeNode(i);
            ret.addAll(merge(lr, rr, mid));
        }
        return ret;
    }

    public List<TreeNode> merge(List<TreeNode> l, List<TreeNode> r, TreeNode mid) {
        List<TreeNode> ret = new ArrayList<>();
        for (int i = 0; i < l.size(); i++) {
            for (int j = 0; j < r.size(); j++) {
                TreeNode nl = copy(l.get(i));
                TreeNode nr = copy(r.get(j));
                TreeNode nm = new TreeNode(mid.val);
                nm.left = nl;
                nm.right = nr;
                ret.add(nm);
            }
        }
        return ret;
    }

    public TreeNode copy(TreeNode t){
        if(t == null){
            return null;
        }
        TreeNode ret = new TreeNode(t.val);
        ret.left = copy(t.left);
        ret.right = copy(t.right);
        return ret;
    }
}
